package com.example.demo.linkedlist;

import java.util.HashMap;
import java.util.Map;

/**
 * @description 基于数组实现 LRU（Least Recently Used 最少使用策略）
 * 1. 空间/时间复杂度都为O(n)
 * 2. 不支持null的缓存
 * @auther lijiewei
 * @date 2021/8/16 15:17
 */
public class LRUBasedArray<T> {

    /** 默认容量. */
    private static final int DEFAULT_CAPACITY = 8;
    /** 容量. */
    private int capacity;
    /** 数量. */
    private int count;
    /** 存放的数组. */
    private T[] value;
    /** 元素和序号的映射. */
    private Map<T, Integer> holder;

    public LRUBasedArray() {
        this(DEFAULT_CAPACITY);
    }

    public LRUBasedArray(int capacity) {
        this.capacity = capacity;
        value = (T[]) new Object[capacity];
        this.count = 0;
        holder = new HashMap<>(capacity);
    }

    /**
     * 添加元素
     * @param object 元素
     * @return
     * @author lijiewei
     * @date   2021/8/16 15:28
     */
    public void add(T object) {
        if (null == object) {
            throw new IllegalArgumentException("该缓存容器不支持null");
        }
        Integer index = holder.get(object);
        if(null == index) {
            //满数组，删除数组最后一位，将元素插入第一位
            if(this.isFull()) {
                removeAndCache(object);
            } else {
                //将元素插入第一位
                cache(object, count);
            }
        } else {
            //更新元素位置
            update(index);
        }
    }

    /**
     * 是否为满数组
     * @return
     * @author lijiewei
     * @date   2021/8/16 15:38
     */
    public boolean isFull() {
        return count == capacity;
    }

    /**
     * 移除数组中指定元素，并重新缓存到数组首位
     * @param object 元素
     * @return
     * @author lijiewei
     * @date   2021/8/16 15:43
     */
    private void removeAndCache(T object) {
        //查找数组最后一位元素，并从映射关系中移除
        T lastObj = value[--count];
        holder.remove(lastObj);
        cache(object, count);
    }

    /**
     * 右移数组中 end 前元素，首位插入元素 object
     * @param object 元素
     * @param end 临界序号
     * @return
     * @author lijiewei
     * @date   2021/8/16 15:45
     */
    private void cache(T object, int end) {
        rightShift(end);
        value[0] = object;
        holder.put(object, 0);
        count++;
    }

    /**
     * 右移数组中 end 前元素
     * @param end 临界序列化
     * @return
     * @author lijiewei
     * @date   2021/8/16 15:54
     */
    private void rightShift(int end) {
        for (int i = end-1; i >=0 ; i--) {
            value[i+1] = value[i];
            holder.put(value[i], i+1);
        }
    }

    /**
     * 更新元素到数组第一位置
     * @param index 序号
     * @return
     * @author lijiewei
     * @date   2021/8/16 16:10
     */
    private void update(int index) {
        T object = value[index];
        rightShift(index);
        value[0] = object;
        holder.put(object, 0);
    }

    public void printAll() {
        for (int i = 0; i < count; i++) {
            System.out.print(value[i] + " ,");
        }
        System.out.println();
    }
}
